Subject: Re: Conservative Sorting/Presv Order of Orig??
From: [email-masked] (Lawrence Kirby)
Date: Sun, 24 Apr 1994 15:26:17 +0000
Newsgroups: comp.programming

In article <[email-masked]>
           [email-masked] "Robert H. Cudmore" writes:

>Hello all,
>
>        I am attempting to sort an array of elements A.  I have a Heap sort
>up and running, the problem is this:  I need the elements with equal keys
>to remain in their original order.  Heap sort with building(hiring) and 
>Sorting(firing) of the array into a heap and then into a sorted array seems
>to cause the destruction of the original order of all elements. 

Sorts which preserve the order of equal keys are described as 'stable' sorts.

>        Are there efficient O(nlogn) sorting routines that will preserve this
>original order?  Quicksort seems to do the same destructive ordering of
>the data where as a simple insertion sort does not.  I would like to stay
>away from linear complexity sorts and would also like to know if I can't
>stay away from them.

Heapsort and Quicksort are not stable. Mergesort is stable, guaranteed O(nlogn)
in the worst case and is just about the fastest of the O(nlogn) sorts. However
if you are sorting arrays rather than lists it requires extra workspace (e.g.
an extra array of n pointers).

You can always make any sort stable by adding a secondary key for
each element which you initialise in ascending order before starting the
sort.

-- 
-----------------------------------------
Lawrence Kirby | [email-masked]
Wilts, England | [email-masked]
-----------------------------------------